#include <iostream>
using std::endl;
using std::cout;
using std::cin;

#include <vector>
using std::vector;

struct matrixTerm
{ // 三元组结构体定义
    int row, col, value;
    matrixTerm &operator=(const matrixTerm &x)
    { // 运算符重载 ，赋值*this = x
        row = x.row;
        col = x.col;
        value = x.value;
        return *this;
    }

    matrixTerm(int row_ = 0, int col_ = 0, int val_ = 0)
        : row(row_)
        , col(col_)
        , value(val_)
    {

    }
};
const int maxsize = 199999; // 新matrixTerm创建最大容量设定

class sparseMatrix // 稀疏矩阵类定义
{
private:
    int Rows;            // 行
    int Cols;            // 列
    int Terms;           // 非零元素个数
    std::vector<matrixTerm> element; // 用来存非零元素的数组
    int maxSize;         // 数组最大容量
public:
    sparseMatrix(int n, int m) // 构造函数
        : element(199999)
    {
        //element = new matrixTerm[maxsize];
        Rows = n;
        Cols = m;
        Terms = 0;
    }

    sparseMatrix(int n, int m, int size, double x) // 构造函数
        : element(size)
    {
        //element = new matrixTerm[maxsize];
        Rows = n;
        Cols = m;
        Terms = 0;
    }

    sparseMatrix(int n, int m, int my) // 构造函数
    {
        //element = new matrixTerm[maxsize];
        Rows = n;
        Cols = m;
        Terms = 0;
    }

    sparseMatrix(int n, int m, char x) // 构造函数
    {
        //element = new matrixTerm[maxsize];
        std::vector<matrixTerm> element1(199999);
        element = element1;
        Rows = n;
        Cols = m;
        Terms = 0;
    }

    void clear();
    int get(int row, int col) const;
    // ~sparseMatrix() { delete[] element; } // 析构函数
    sparseMatrix &operator=(sparseMatrix &a)
    { // 运算符重载 ，赋值*this = a
        Rows = a.Rows;
        Cols = a.Cols;
        Terms = a.Terms;
        maxSize = a.maxSize;
        // for (int i = 0; i < Terms; i++)
        //     element[i] = a.element[i];
        element = a.element;
        return *this;
    }
    void inputAelement(int x, int y, int v); // 辅助函数——非0值输入
    void initial();              // 重置1
    int multiply(sparseMatrix &a);           // 乘法2
    int add(sparseMatrix &a);                // 加法3
    void output();                           // 输出4
    void transpose();                        // 转置5
};

// 辅助函数——非0值输入，更新三元组
void sparseMatrix::inputAelement(int x, int y, int v)
{
    matrixTerm New;
    New.row = x;   // 行序号
    New.col = y;   // 列序号
    New.value = v; // 非零元素值
    //element[Terms] = New;
    element.push_back(New);
    Terms++;
}

void sparseMatrix::clear()
{
    Rows = 0;
    Cols = 0;
    Terms = 0;
    element.clear();
}

// 重置1
void sparseMatrix::initial()
{
    clear();
    int n = 0;
    int m = 0;
    cin >> n >> m;
    Rows = n;
    Cols = m;
    Terms = 0;
    for (int i = 1; i <= Rows; ++i)
    { // 按行优先顺序输入矩阵的各个元素
        for (int j = 1; j <= Cols; ++j)
        {
            int b;
            cin >> b;
            if (b != 0)
            {
                matrixTerm tmp(i, j, b);
                element.push_back(tmp);
                // element[Terms].row = i;
                // element[Terms].col = j;
                // element[Terms].value = b;
                Terms++;
            }
        }
    }
}

// 乘法2
int sparseMatrix::multiply(sparseMatrix &Q)
{
    // 有效性检验
    if (Cols != Q.Rows)
    { // 按矩阵乘法C[m,n]= P[m,k] ×Q[k,n]，需要有Cols=Q.Rows
        *this = Q;
        return -1;
    }
    else
    {
        // // 取乘数P的行和乘数Q的列构建结果sparseMatrix
        // sparseMatrix C(Rows, Q.Cols);
        // int num[10000];    // 每行非零元素的个数
        // int Index[10000];  // 每行第一个非零元素对应的索引
        // int Answer[10000]; // 存放乘法结果
        // // 每行计数清零
        // for (int i = 1; i <= Q.Rows; i++)
        //     num[i] = 0;
        // // 计数得第i行对应非零元素个数
        // for (int i = 0; i < Q.Terms; i++)
        // {
        //     num[Q.element[i].row]++;
        // }
        // // 第i行第一个非零元素索引
        // Index[1] = 0;
        // for (int i = 2; i <= Q.Terms; i++)
        //     Index[i] = Index[i - 1] + num[i - 1];
        // // 开始乘法计算C[m,n]= P[m,k] ×Q[k,n]
        // int p = 0;
        // for (int i = 1; i <= Rows && p < Terms; i++)
        // {
        //     // 赋初值0
        //     for (int j = 1; j <= Q.Cols; j++)
        //         Answer[j] = 0;  
        //     while (p < Terms && element[p].row == i) // 循环条件为仍有非零元素且第i行有非零元素
        //     {
        //         int t = element[p].col;
        //         if (num[t] != 0) // P有非0元素的行对应的Q里的列任有非0元素
        //         {                // 如果都是0了，乘法所得也不会是非0，这个判断起简化作用
        //             for (int q = Index[t]; q < Index[t] + num[t]; q++)
        //                 // 计算对应i行每列的乘积
        //                 Answer[Q.element[q].col] += element[p].value * Q.element[q].value;
        //         }
        //         // 继续下一个非零元素
        //         p++;
        //     }
        //     for (int k = 1; k <= Q.Cols; k++)
        //     { // 结果中的非0元素导出三元组
        //         if (Answer[k] != 0)
        //         {
        //             C.element[C.Terms].value = Answer[k];
        //             C.element[C.Terms].row = i;
        //             C.element[C.Terms].col = k;
        //             C.Terms++;
        //         }
        //     }
        // }
        // sparseMatrix tmp(C.Rows, C.Cols, 20);
        // tmp.Terms = C.Terms;
        // for (int i = 0; i < C.Terms; ++i)
        // {
        //     tmp.element.push_back(C.element[i]);
        // }
        // *this = tmp;
        // return 0;

        sparseMatrix m2 = Q;
        // this即是m1
        // m1每行的元素个数
        vector<int> m1_row_count(Rows + 1, 0);
        for (int i = 0; i < element.size(); ++i)
        {
            ++m1_row_count[element[i].row];
        }
        // m1的行指针数组rowidx
        vector<int> m1_rowidx(Rows + 1, 0);
        int m1_cumulative_sum = m1_row_count[1];
        for (int i = 2; i <= Rows; ++i)
        {
            m1_rowidx[i] = m1_cumulative_sum;
            m1_cumulative_sum += m1_row_count[i];
        }

        // m2
        // m2每行的元素个数, 使用的方法是计数数组
        vector<int> m2_row_count(m2.Rows + 1, 0);
        for (int i = 0; i < m2.element.size(); ++i)
        {
            ++m2_row_count[m2.element[i].row];
        }
        // m2的行指针数组rowidx
        vector<int> m2_rowidx(m2.Rows + 1, 0);
        int m2_cumulative_sum = m2_row_count[1];
        for (int i = 2; i <= Rows; ++i)
        {
            m2_rowidx[i] = m2_cumulative_sum;
            m2_cumulative_sum += m2_row_count[i];
        }

        sparseMatrix product(Rows, m2.Cols);

        vector<int> row_sum_array(m2.Cols + 1, 0);
        //row_sum_array.resize(m2.m_col + 1);

        // 求结果矩阵的第i行的非零元素 = m1的第i行的各个元素 * m2的对应行 (列与行对应), 再求和
        for (int i = 1; i <= product.Rows; ++i)
        {
            // 遍历m1的第i行的非零元素, j是存储索引
            for (int j = m1_rowidx[i]; j < m1_rowidx[i] + m1_row_count[i]; ++j)
            {
                // m1第i行 m_terms[j]的非零元素, 其所在列为k = m_terms[j].m_col, 即m1的第i行第k个元素, 与m2的第k行的各个元素相乘
                int k = element[j].col;

                // 遍历m2的第k行的非零元素, p是存储索引
                for (int p = m2_rowidx[k]; p < m2_rowidx[k] + m2_row_count[k]; ++p)
                {
                    // m2第k行 m2.m_terms[p]非零元素, 其所在列为s = m2.m_terms[p].m_col, 即m2的第k行的第s个元素, 与m1第i行的第k个元素相乘, 
                    // 得到结果矩阵(i, s)元素的分量

                    int s = m2.element[p].col;
                    // 结果矩阵(i, p)元素的分项
                    row_sum_array[s] += element[j].value * m2.element[p].value;
                }
            }

            if (m1_row_count[i] != 0)
            {
                for (int c = 1; c <= m2.Cols; ++c)
                {
                    if (row_sum_array[c] != 0)
                    {
                        product.element.push_back(matrixTerm(i, c, row_sum_array[c]));
                        row_sum_array[c] = 0;
                    }

                }
            }
            

            
            
        }

        Rows = product.Rows;
        Cols = product.Cols;
        element.swap(product.element);

        return 0;
        
    }
}



// 加法3
int sparseMatrix::add(sparseMatrix& Q)
{
    if (Q.Cols != Cols || Q.Rows != Rows) // 根据矩阵加法规则，行列不等不符合
    {
        *this = Q;
        return -1;
    }
    else
    {
        sparseMatrix C(Rows, Cols, 10); // 设置结果矩阵的特征
        //C.element.resize(19999);
        int it = 0, ib = 0;
        while (it < element.size() && ib < Q.element.size()) // 遍历，把相关的项相加
        {                                    // 行主索引加上每一项的列数
            int tIndex = (element[it].row-1) * Cols + element[it].col;
            int bIndex = (Q.element[ib].row - 1) * Cols + Q.element[ib].col;
            if (tIndex < bIndex)
            { // Q项在后
                matrixTerm tmp(element[it].row, element[it].col, element[it].value);
                C.element.push_back(tmp);
                it++;
              
            }
            else if (tIndex == bIndex)
            { // 两项在同一个位置
                if ((element[it]).value + (Q.element[ib]).value != 0)
                { // 仅当相加后不为0时加入c
                    matrixTerm tmp(element[it].row, element[it].col, element[it].value + Q.element[ib].value);
                    C.element.push_back(tmp);
                    
                }
                it++;
                ib++;
            }
            else
            {
                matrixTerm tmp(Q.element[ib].row, Q.element[ib].col, Q.element[ib].value);
                C.element.push_back(tmp);
                ib++;
                
            }
        }
        // 复制剩余项
        while (it < element.size())
        //for (; it < element.size(); it++)
        {
            matrixTerm tmp(element[it].row, element[it].col, element[it].value);
            C.element.push_back(tmp);
            
            it++;
        }
        while (ib < Q.element.size())
        //for (; ib < Q.element.size(); ib++)
        {
            matrixTerm tmp(Q.element[ib].row, Q.element[ib].col, Q.element[ib].value);
            C.element.push_back(tmp);
            
            ib++;
        }

        C.Terms = C.element.size();
        //*this = C;

        Rows = C.Rows;
        Cols = C.Cols;
        Terms = C.Terms;
        maxSize = C.maxSize;
        //for (int i = 0; i < Terms; i++)
        //    element[i] = a.element[i];
        element = C.element;

        return 0;
    }
}
int sparseMatrix::get(int row, int col) const
{
	for (int i = 0; i < element.size(); ++i)
	{
		if (element[i].row == row && element[i].col == col)
		{
			return element[i].value;
		}
		else if (element[i].row > row)
		{
			break;
		}
		else if (element[i].row == row && element[i].col > col)
		{
			break;
		}
	}

	return 0; // 这一点就受限了该类的数据类型只能为数值型
}

// 输出4
void sparseMatrix::output()
{
    int i, j, k = 0;
    cout << Rows << " " << Cols << endl;
    for (i = 1; i <= Rows; i++) // 遍历输出
    {
        for (j = 1; j <= Cols; j++)
        {
            //cout << get(i, j) << " ";
            if (k < Terms && element[k].row == i && element[k].col == j)
            {
                cout << element[k].value << " ";
                k++;
            }
            else
                cout << 0 << " ";
        }
        cout << endl;
    }
}



// 转置5
void sparseMatrix::transpose()
{
    // 设置转置矩阵特征
    sparseMatrix b(Cols, Rows, element.size(), 3.14);
    b.Terms = Terms;
    
    // 初始化
    vector<int> colSize(Cols+1, 0); // 矩阵第i列的非零元素个数
    vector<int> rowNext(Cols + 1, 0); // 矩阵第i列第一个非零元素索引

    // 计算待转置矩阵中每一列非0元素的个数
    for (int i = 0; i < element.size(); i++)
        colSize[element[i].col]++;
    
    // 确定矩阵第i列第1个非0元素的对应索引
    // int accumulation = colSize[1];
    // for (int i = 2; i <= Cols; i++)
    // {
    //     rowNext[i] = accumulation;
    //     accumulation += colSize[i];

    // }
    int accumulation = colSize[1];
    for (int i = 2; i <= Cols; i++)
    {
        rowNext[i] = accumulation;
        accumulation += colSize[i];
    }
    // 上述几步和乘法中同理，提高程序针对稀疏矩阵运算效率

    // 实施从*this到b的转置复制
    for (int i = 0; i < Terms; i++)
    {
        int j = rowNext[element[i].col];
        // 行列转置
        b.element[j] = matrixTerm(element[i].col, element[i].row, element[i].value);
        // b.element[j].row = element[i].col;
        // b.element[j].col = element[i].row;
        // b.element[j].value = element[i].value;
        rowNext[element[i].col] = rowNext[element[i].col] + 1;
        // 对应列rowNext索引+1，以防同一列有多个非零元素 (防撞）
    }

    *this = b;
}

int main()
{
    sparseMatrix P(0, 0, 20);
    int w;           // 操作个数
    int panduan = 0; // 各种不合法输出工具变量
    int n;           // 矩阵行数
    int m;           // 矩阵列数
    int t;           // 矩阵非0元素个数
    int trans;       // 操作编码
    cin >> w;
    for (int i = 0; i < w; i++)
    {
        cin >> trans;
        switch (trans)
        {
            // 重置矩阵
            case 1:
            {
                P.initial();
                break;
            }

            // 矩阵乘法
            case 2:
            {
                cin >> n >> m;
                cin >> t;
                sparseMatrix Q1(n, m, 20);
                for (int i = 0; i < t; i++)
                {
                    // Q矩阵非零元素的行、列序号及非0元素值
                    int x, y, v;
                    cin >> x >> y >> v;
                    Q1.inputAelement(x, y, v);
                }
                panduan = P.multiply(Q1);
                if (panduan == -1)
                    cout << panduan << endl;
                break;
            }

            // 矩阵加法
            case 3:
            {
                cin >> n >> m;
                cin >> t;
                sparseMatrix Q2(n, m, 20);
                for (int i = 0; i < t; i++)
                {
                    int x, y, v;
                    cin >> x >> y >> v;
                    Q2.inputAelement(x, y, v);
                }
                panduan = P.add(Q2);
                if (panduan == -1)
                    cout << panduan << endl;
                break;
            }

            // 输出操作
            case 4:
            {
                P.output();
                break;
            }

            // 转置
            case 5:
            {    
                P.transpose();
                break;
            }


        }
    } 
    return 0;
}